package depth_first_search;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */

import java.util.Comparator;
import java.util.PriorityQueue;


public class DepthFirstSearch2D {
	
	private Maze2D maze2d;
	Dimension path[];
	Dimension shortestPath[];
	boolean isVisited2D[][];
	boolean pathFound=false;
	Comparator<Dimension> comparator;
	
	/*
	 * CONSTRUCTOR FOR INITIALIZING maze2d.
	 */
	public DepthFirstSearch2D(Maze2D maze){
		maze2d=maze;
		int n=maze2d.n;
		path=new Dimension[n*n];
		isVisited2D=new boolean[n][n];
		comparator=(Comparator<Dimension>) new CellComparator(new Dimension(maze.goalLoc.getX(),maze.goalLoc.getY())); // A comparator for comparing cells.
	}
	
												//2D MAZE
	
	
	/*
	 * FUNCTION TO SEARCH THE SHORTEST PATH IN A 2D MAZE.
	 */
	public void doSearchOn2DMaze(){
		path[0]=maze2d.startLoc;
		isVisited2D[maze2d.startLoc.getX()][maze2d.startLoc.getY()]=true;
		DFS2D(maze2d.startLoc,1);
	}
	
	
	/*
	 *HELPER FUNCTION FOR THE FUNCTION doSearchOn2DMaze(). 
	 */
	public void DFS2D(Dimension u,int i){
		
		if(pathFound)
			return;
		
		//THE CURRENT CELL u HAS BEEN VISITED WITH THIS RECURSIVE CALL
		isVisited2D[u.getX()][u.getY()]=true;
		
		//CONSTRUCT A PRIORITYQUEUE INSTEAD OF A STACK TO STORE ALL POSSIBLE VALID MOVES FROM THE CURRENT CELL u.
		//Stack<Dimension> s=new Stack<Dimension>();
		PriorityQueue<Dimension> pq=new PriorityQueue<Dimension>(4,comparator);
		
		
		//CHECK WHETHER THE GOAL CELL HAS BEEN REACHED.
		int a=u.getX();
		int b=u.getY();
		if(a==maze2d.goalLoc.getX() && b==maze2d.goalLoc.getY()){
			//System.out.println("a path found");
			displayPath2D(i);
			pathFound=true;
		}
		
		//FIND VALID MOVES FROM THE CURRENT CELL AND PUSH THEM INTO THE PRIORITY QUEUE.
		if(a-1>=0 && maze2d.maze[a-1][b]==maze2d.VALID_CELL && !isVisited2D[a-1][b]){
			pq.offer(new Dimension(a-1,b));
		}
		if(a+1<maze2d.n && maze2d.maze[a+1][b]==maze2d.VALID_CELL && !isVisited2D[a+1][b]){
			pq.offer(new Dimension(a+1,b));
		}
		if(b-1>=0 && maze2d.maze[a][b-1]==maze2d.VALID_CELL && !isVisited2D[a][b-1]){
			pq.offer(new Dimension(a,b-1));
		}
		if(b+1<maze2d.n && maze2d.maze[a][b+1]==maze2d.VALID_CELL && !isVisited2D[a][b+1]){
			pq.offer(new Dimension(a,b+1));
		}
		while(!pq.isEmpty()){
			Dimension v=(Dimension) pq.poll();
			path[i]=v;
			DFS2D(v,i+1);
			
		}
		
		//WHEN RETURNING FROM THE CELL, REMEMBER TO NEGATE THE isVisited FLAG FOR THAT CELL.
		isVisited2D[u.getX()][u.getY()]=false;
	}
	
	/*
	 * DISPLAY THE PATH IN THE 2D MAZE AND STORE THE RESULT IN shortestPath.
	 */
	public void displayPath2D(int depth){
		int k=0;
		shortestPath=new Dimension[depth];
		System.out.println(path[k].getX()+" , "+path[k].getY());
		shortestPath[k]=new Dimension(path[k].getX(),path[k].getY());
		k++;
		while(k<depth){
			System.out.println(path[k].getX()+" , "+path[k].getY());
			shortestPath[k]=new Dimension(path[k].getX(),path[k].getY());
			k+=1;
		}
	}
	
	
}
